import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.StringTokenizer;


public abstract class Ejercicio
{
        public void execute(String strFileIn, String strFileOut)
        {
                //archivo entrada
                RandomAccessFile fin;
                //para borrar la salida anterior
                File foutDelete;
                //archivo salida
                RandomAccessFile fout;

                try
                {
                        //abro el archivo
                        fin = new RandomAccessFile(strFileIn,"r");

                        //buffer de entrada y salida
                        String strOutBuffer = "", strInBuffer = fin.readLine();
                        //auxiliares
                        int i, j, n1, v1[], n2, v2[], m, np1, vp1[], np2, vp2[], mp, a, b;
                        //eje auxiliar
                        Eje v1v2[], vp1vp2[];
                        //para recorrer la linea del arreglo
                        StringTokenizer stk;
                        //resultado
                        Resultado res;

                        //mientras haya mas lineas
                        while(strInBuffer != null)
                        {
                                //cantidad de vertices del conjunto v1
                                n1 = new Integer(strInBuffer).intValue();

                                //genero el conjunto vertices v1
                                v1 = new int[n1];

                                //siguiente linea
                                strInBuffer = fin.readLine();

                                for( i = 0; i < n1; i++ )
                                {
                                        v1[i] = new Integer(strInBuffer).intValue();

                                        //siguiente linea
                                        strInBuffer = fin.readLine();
                                }

                                //cantidad de vertices del conjunto v2
                                n2 = new Integer(strInBuffer).intValue();

                                //genero el conjunto vertices v1
                                v2 = new int[n2];

                                //siguiente linea
                                strInBuffer = fin.readLine();

                                for( i = 0; i < n2; i++ )
                                {
                                        v2[i] = new Integer(strInBuffer).intValue();

                                        //siguiente linea
                                        strInBuffer = fin.readLine();
                                }

                                //cantidad de aristas de v1 a v2
                                m = new Integer(strInBuffer).intValue();

                                //genero el conjunto de aristas de v1 a v2
                                v1v2 = new Eje[m];

                                //siguiente linea
                                strInBuffer = fin.readLine();

                                for( i = 0; i < m; i++ )
                                {
                                        //separo la linea por los espacios
                                        stk = new StringTokenizer( strInBuffer, " " );

                                        //creo el eje
                                        v1v2[i] = new Eje();

                                        //si quedaron dos elementos
                                        if( stk.countTokens() == 2 )
                                        {
                                                a = new Integer( stk.nextToken() ).intValue();
                                                b = new Integer( stk.nextToken() ).intValue();

                                                j = 0;

                                                while( j < n1 && v1[j] != a )
                                                        j++;

                                                if( j < n1 )
                                                {
                                                        v1v2[i].origen = a;
                                                        v1v2[i].destino = b;
                                                }
                                                else
                                                {
                                                        v1v2[i].origen = b;
                                                        v1v2[i].destino = a;
                                                }
                                        }

                                        //siguiente linea
                                        strInBuffer = fin.readLine();
                                }

                                //cantidad de vertices del conjunto vp1
                                np1 = new Integer(strInBuffer).intValue();

                                //genero el conjunto vertices vp1
                                vp1 = new int[np1];

                                //siguiente linea
                                strInBuffer = fin.readLine();

                                for( i = 0; i < np1; i++ )
                                {
                                        vp1[i] = new Integer(strInBuffer).intValue();

                                        //siguiente linea
                                        strInBuffer = fin.readLine();
                                }

                                //cantidad de vertices del conjunto vp2
                                np2 = new Integer(strInBuffer).intValue();

                                //genero el conjunto vertices vp1
                                vp2 = new int[np2];

                                //siguiente linea
                                strInBuffer = fin.readLine();

                                for( i = 0; i < np2; i++ )
                                {
                                        vp2[i] = new Integer(strInBuffer).intValue();

                                        //siguiente linea
                                        strInBuffer = fin.readLine();
                                }

                                //cantidad de aristas de vp1 a vp2
                                mp = new Integer(strInBuffer).intValue();

                                //genero el conjunto de aristas de vp1 a vp2
                                vp1vp2 = new Eje[mp];

                                //siguiente linea
                                strInBuffer = fin.readLine();

                                for( i = 0; i < mp; i++ )
                                {
                                        //separo la linea por los espacios
                                        stk = new StringTokenizer( strInBuffer, " " );

                                        //creo el eje
                                        vp1vp2[i] = new Eje();

                                        //si quedaron dos elementos
                                        if( stk.countTokens() == 2 )
                                        {
                                                a = new Integer( stk.nextToken() ).intValue();
                                                b = new Integer( stk.nextToken() ).intValue();

                                                j = 0;
                                                int k = 0;
                                                while( j < n1 && v1[j] != a )
                                                    j++;
                                                while( k < np1 && vp1[k] != a )
                                                    k++;

                                                if( j+k < n1+np1 )
                                                {
                                                        vp1vp2[i].origen = a;
                                                        vp1vp2[i].destino = b;
                                                }
                                                else
                                                {
                                                        vp1vp2[i].origen = b;
                                                        vp1vp2[i].destino = a;
                                                }
                                        }

                                        //siguiente linea
                                        strInBuffer = fin.readLine();
                                }

                                //obtengo el resultado
                                res = DGIB
                                (
                                                n1, v1, n2, v2, m, v1v2,
                                                np1, vp1, np2, vp2, mp, vp1vp2
                                );

                                //guardo la salida
                                if(strOutBuffer != "")
                                        strOutBuffer+= "\n";

                                strOutBuffer+= res.kid;
                                strOutBuffer+= "\n";
                                strOutBuffer+= res.n_iv1;

                                for(i = 0; i < res.n_iv1; i++)
                                {
                                        strOutBuffer+= " ";
                                        strOutBuffer+= res.iv1[i];
                                }

                                strOutBuffer+= "\n";
                                strOutBuffer+= res.n_iv2;

                                for(i = 0; i < res.n_iv2; i++)
                                {
                                        strOutBuffer+= " ";
                                        strOutBuffer+= res.iv2[i];
                                }
                        }

                        //cierro el archivo
                        fin.close();

                        //borro el archivo de salida anterior
                        foutDelete = new File(strFileOut);
                        foutDelete.delete();

                        //abro el archivo de salida
                        fout = new RandomAccessFile(strFileOut,"rw");

                        //paso el buffer de salida al archivo
                        fout.writeBytes(strOutBuffer);

                        //cierro el archivo de salida
                        fout.close();
                }
                catch (IOException e)
                {
                        //TODO: error abriendo archivo
                }
        }


    public int cantidadCruces
    (
        int V[], int n,
        int V2[], int n2,
        Eje vv2[], int m
     ){ 
        int i, j, cruces = 0; Eje e1, e2;
        //calculo las posiciones de cada nodo
        int[] vpos = new int[n+n2];
        
        for( i = 0; i < n; i++ ) 
        	vpos[V[i]-1] = i;
        
        for( i = 0; i < n2; i++ ) 
        	vpos[V2[i]-1] = i;
        
        //por cada eje sin contar el primero 
        for( i = 1; i < m; i++ )
        { 
        	e1 = vv2[i];
        	
        	//me fijo los ejes anteriores 
        	for( j = 0; j < i; j++ ) 
        	{ 
        		e2 = vv2[j];
        	
        		if(  
		    			//si el eje nuevo sale desde abajo del otro 
		    			( vpos[e1.origen-1] < vpos[e2.origen-1] 
		    			//y llega mas arriba que el otro 
		    			&& vpos[e1.destino-1] > vpos[e2.destino-1] )
		    			//o  
		    			//si el eje nuevo sale desde arriba del otro 
		    			||( vpos[e1.origen-1] > vpos[e2.origen-1] 
		    			//y llega mas abajo que el otro 
		    			&& vpos[e1.destino-1] < vpos[e2.destino-1] ) 
        		)
        		{ 
        			//entonces se cruzan 
        			cruces++; 
        		}  
        	}
        }
        return cruces; 
    }
    
    public int CrucesDelEje
    (
            Nodo V[], int n,
            Nodo V2[], int n2,
            Eje vv2[], int m,
            Eje e
    ){
        int i, cruces = 0; Eje e2;
        //calculo las posiciones de cada nodo
        int[] vpos = new int[n+n2];
        
        for( i = 0; i < n; i++ ) 
        	vpos[V[i].valor -1] = i;
        
        for( i = 0; i < n2; i++ ) 
        	vpos[V2[i].valor -1] = i;
        
        for(i = 0; i < m; i++ )
        {
        	e2 = vv2[i];
        	
    		if(  
	    			//si el eje nuevo sale desde abajo del otro 
	    			( vpos[e.origen-1] < vpos[e2.origen-1] 
	    			//y llega mas arriba que el otro 
	    			&& vpos[e.destino-1] > vpos[e2.destino-1] )
	    			//o  
	    			//si el eje nuevo sale desde arriba del otro 
	    			||( vpos[e.origen-1] > vpos[e2.origen-1] 
	    			//y llega mas abajo que el otro 
	    			&& vpos[e.destino-1] < vpos[e2.destino-1] ) 
    		)
    		{ 
    			//entonces se cruzan 
    			cruces++; 
    		}  
        }
        
    	return cruces;
    }

    public int CrucesDelEje
    (
            int V[], int n,
            int V2[], int n2,
            Eje vv2[], int m,
            Eje e
    ){
        int i, cruces = 0; Eje e2;
        //calculo las posiciones de cada nodo
        int[] vpos = new int[n+n2];
        
        for( i = 0; i < n; i++ ) 
        	vpos[V[i]-1] = i;
        
        for( i = 0; i < n2; i++ ) 
        	vpos[V2[i]-1] = i;
        
        for(i = 0; i < m; i++ )
        {
        	e2 = vv2[i];
        	
    		if(  
	    			//si el eje nuevo sale desde abajo del otro 
	    			( vpos[e.origen-1] < vpos[e2.origen-1] 
	    			//y llega mas arriba que el otro 
	    			&& vpos[e.destino-1] > vpos[e2.destino-1] )
	    			//o  
	    			//si el eje nuevo sale desde arriba del otro 
	    			||( vpos[e.origen-1] > vpos[e2.origen-1] 
	    			//y llega mas abajo que el otro 
	    			&& vpos[e.destino-1] < vpos[e2.destino-1] ) 
    		)
    		{ 
    			//entonces se cruzan 
    			cruces++; 
    		}  
        }
        
    	return cruces;
    }
    
	public void swap( Nodo v[], int a, int b )
	{
		Nodo n = v[a];
		v[a] = v[b];
		v[b] = n;
	}
	
	public void swap( int v[], int a, int b )
	{
		int n = v[a];
		v[a] = v[b];
		v[b] = n;
	}
	
	public void swap( Grado v[], int a, int b )
	{
		Grado n = v[a];
		v[a] = v[b];
		v[b] = n;
	}

	public boolean esta(int [] V, int e)
	{
		boolean r = false;

		for(int k = 0; k < V.length && !r; k++)
		{
			if(V[k] == e)
				r = true;
		}

		return r;
	}

	public boolean esta(Nodo [] V, int e)
	{
		boolean r = false;

		for(int k = 0; k < V.length && !r; k++)
		{
			if(V[k].valor == e)
				r = true;
		}

		return r;
	}

	public class Grado
	{
		int grado;
		int valor;
		
		public Grado(int v, int g)
		{
			valor = v;
			grado = g;
		}
	}
	
	protected abstract Resultado DGIB
	(
			int n1, int v1[], int n2, int v2[], int m, Eje v1v2[],
			int np1, int vp1[], int np2, int vp2[], int mp, Eje vp1vp2[]
	);
}
